class Solution {

    /**
     * 作者：力扣官方题解
     *  链接：https://leetcode.cn/problems/ransom-note/solutions/1135839/shu-jin-xin-by-leetcode-solution-ji8a/
     *  来源：力扣（LeetCode）
     *  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 
     * T(n) = O(m+n)
     */
    public boolean canConstruct0(String ransomNote, String magazine) {
        // 当rn长度比mgz长度还长时，必然不可能组成
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) { // toCharArray() 变成字符数组
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
    
    public boolean canConstruct1(String ransomNote, String magazine) {
        // magazine中，每个字母的搜索范围，每次搜索从该位置开始
        int[] pos = new int[26];
        for (char c : ransomNote.toCharArray()) {
            int index = c-'a';
            // 如果找到该字母，则将搜索范围置于该字母位置之后
            pos[index] = magazine.indexOf(c,pos[index])+1; 
            // 如果没找到，则indexOf返回-1， pos[index]为0，不能组成
            if(pos[index]==0){
                return false;
            }
        }
        return true;
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> map = new HashMap<>();
        char c;
        for (int i = 0; i < magazine.length(); i++) {
            c = magazine.charAt(i);
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            c = ransomNote.charAt(i);
            if (map.get(c) != null && map.get(c) > 0){
                map.put(c, map.getOrDefault(c,0) - 1);
            } else {
                return false;
            }
        }
        return true;
    }
}